package main

import (
	"sort"
)

/*
	有一个总空间为100字节的堆，现要从中新申请一块内存，内存分配原则为：优先紧接着前一块已使用内存，分配空间足够且最接近申请大小的空闲内存。
	第1行是1个整数，表示期望申请的内存字节数
	第2到第N行是用空格分割的两个整数，表示当前已分配的内存的情况，每一行表示一块已分配的连续内存空间，每行的第1和第2个整数分别表示偏移地址和内存块大小，如：
	0 1
	3 2
	表示 0 偏移地址开始的 1 个字节和 3 偏移地址开始的 2 个字节已被分配，其余内存空闲。
*/

func main() {
	println(getResult4([][2]int{{0, 1}, {3, 2}}, 1))
}
func getResult4(arr [][2]int, size int) int {
	if size < 0 || size > 100 {
		return -1
	}
	sort.Slice(arr, func(i, j int) bool {
		return arr[i][0] < arr[j][0]
	})
	freeOffset := 0
	mallocOffset := -1
	// 记录最接近申请内存的空闲内存块大小
	minMallocSize := 100
	offset := 0
	for i := 0; i < len(arr); i++ {
		offset = arr[i][0]
		// 如果占用的内存起始位置 小于 前面一个空闲内存块起始位置，则存在占用内存区域重叠
		// 如果占用的内存起始位置 大于 99，则非法
		if offset < freeOffset || offset > 99 {
			return -1
		}
		if offset > freeOffset {
			freeMemorySize := offset - freeOffset
			if freeMemorySize >= size && freeMemorySize < minMallocSize {
				mallocOffset = freeOffset
				minMallocSize = freeMemorySize
			}
		}
		freeOffset = offset + arr[i][1]
	}
	lastFreeMemorySize := 100 - freeOffset
	if lastFreeMemorySize >= size && lastFreeMemorySize < minMallocSize {
		mallocOffset = freeOffset
	}
	return mallocOffset
}
